The invention pertains to computer network protocols and computer programs that implement such protocols.
There are many instances in which it would be advantageous to be able to advance and retard data transfer rates during network data transmissions to make full use of the available bandwidth based on the current network traffic. One such instance occurs when multi-player games are played over a network, such as the Internet. The executable code for these games are often located on network servers that are accessible through various networks, such as the Internet. Alternately, some or all of the executable code for the games may be located on each of computers the players are using. One or more players can log on to the game and play against the game itself (a computer) or each other. These games typically comprise an ever-changing graphical environment that is primarily controlled by the control inputs of the various game players. For example, a game may involve several warriors facing off against one another, with one or more of the warriors being controlled by each player (or a computer). In such a game, the movements of each warrior relative to the graphical environment and the other warriors will depend on the control inputs of the players (or automated movements by the computer). For this reason, it is highly desired to transfer the user-input information to the game as rapidly as possible so that the inputs for the various players can be immediately reflected by updating the graphics displayed on each player""s screen.
To understand why rapid data transfer is so desirable, consider a situation in which the data transfer carries a substantial delay. Player A activates her controls to cause one of her warriors to throw a spear at an enemy warrior. Player A aims the spear based on her perception of the current state of the game, i.e., what she sees on her screen. If the data transfer rate is rapid, the display each player sees accurately reflects (is synchronous with) the current state of the game. Conversely, if the data transfer carries a delay, the display each player sees does not accurately reflect the present game statexe2x80x94that is, the displays observed by the various players will not be synchronized. Under such circumstances, the players may miss their targets due to the program""s inaccurate display of the positions of the other participants. This delay may also cause players to be unaware of an attack in progress from another player. Transfer delays of this type are frequently encountered when networked games are played, creating unsatisfactory game performance. A principle reason for this is conventional program development tools do not provide a built-in interface that allows the data transfer rate to be adjusted to optimize bandwidth use under varying link conditions.
Developers of multi-player networked game applications typically design games to support presumed worst-case bandwidth situations. As a result, the bandwidth usage between machines is limited to a fraction of the bandwidth available over the network link, which results in non-optimal game performance. Under such worst-case-scenario design practices, the game developer assumes a minimum available link bandwidth, such as 14.4 or 28.8 kilobaud (kilobits per second), and a maximum number of players the game will support or likely encounter. The developer may also determine the average (or maximum) size of each message that the game will transfer over the network (which she typically will seek to minimize). The developer will then calculate a maximum message sending rate based on this predetermined criteria, and the game application will send messages at this calculated transfer rate. For example, in a peer-to-peer game, where messages are distributed to all players from each machine, the following equation can be used to determine the maximum sending rate:                     R        =                  bw                      cb            *                          (                              n                -                1                            )                                                          (        1        )            
wherein R is the maximum message sending rate in messages per second, n is the number of players in the game, cb is the number of bytes in a message, and bw is the assumed bandwidth.
Unfortunately, the use of static calculations of this sort leads to a number of problems, including: (1) the application can""t compensate for variation in headers due to the underlying transport; (2) the application will under-utilize the link in situations where more bandwidth is available than originally presumed; and (3) the application will not be able to adjust the message sending rate to compensate for other traffic on the link. In addition, when the conditions on the link are actually worse than the initial assumptions, sending messages at the statically-determined rate will lead to the link being backlogged. That is, the rate at which the application sends messages may exceed the link""s capabilities, causing messages to build up in the sending computer or on a router in the network, resulting in increased apparent latency that can grow without bound, eventually making the game unplayable and ultimately causing the link to timeout.
Some multi-user applications send data to remote computers using a non-reliable transport. A non-reliable transport is a transport that does not guarantee delivery. While such protocols eliminate the overhead associated with ensuring delivery of a message, they have the significant drawback that any message may not reach its destination. This particularly is a problem when the lost message contains critical game-state information. One way to address this problem is to send messages over two separate logical links, where critical messages are sent using a reliable transport, and non-critical messages are sent using a non-reliable transport.
Such a scheme is illustrated in FIG. 7, where an application 302 sends both critical messages 304 and non-critical messages 306. The critical messages 304 are sent over a reliable transport such as TCP transport layer protocol 308, which operates on top of an IP network layer protocol 310. The combined services of the TCP protocol 308 and the IP protocol 310 support a reliable communications link 312. Conversely, non-critical messages 306 are sent over a non-reliable transport such as the UDP transport layer protocol 314, which also operates on top of an IP network layer protocol 316 to support a non-reliable communications link 318.
A primary drawback of the FIG. 7 scheme is that it requires two distinct protocols at the transport layer, namely TCP and UDP. TCP and UDP provide different services implemented in distinct programs. When used to send data between local and remote application programs, each operates independently. In particular, when a local application program wants to send critical data via TCP and non-critical data via UDP, it invokes the TCP and UDP protocols separately. In these circumstances, the TCP and UDP protocols operate independently and do not share operational data. The operation of one protocol can impact the operation of another protocol. For example, the available bandwidth that the TCP protocol will experience varies depending on whether the UDP protocol is sending messages at the same time. Since the protocols do not share operational data, the UDP protocol has no way to get operational data from the TCP protocol. As such, the local computer has no mechanism for effectively tuning the send rate across concurrently executing protocols.
The invention addresses these and other drawbacks by providing a network communication protocol that allows application programs to send messages over both reliable and non-reliable channels that share a single communications link. The protocol and related methods additionally allow simultaneous tuning of both channels to optimize the available network bandwidth under varying network conditions. The network protocol is preferably implemented as an application program interface (API) that allows programmers to use features of the invention through a set of API calls. The network protocol resides at the application layer, providing an interface to the underlying transport services so that the application program does not need to be concerned with how messages are being transported.
In one aspect of the invention, the network protocol enables application programs to use a reliable channel and a non-reliable channel over the same network communications link between a local and remote computer. The network protocol facilitates reliable and non-reliable channels on a single network link with a set of message header data structures, the first header being used for outbound and resend messages, and the second header for acknowledge messages. The outbound message header includes an acknowledge request field used to signal the remote computer to send an acknowledgment message indicating that it has successfully received the corresponding outbound message from the local computer.
The network protocol in the local computer uses the acknowledge field to ensure that messages sent over the reliable channel are received. In addition, it uses the acknowledge field for messages sent over the reliable and non-reliable channels to maintain operational data used to tune the network communications link shared by both of these channels. To support reliable transfer, the network protocol monitors for proper acknowledgement and resends reliable messages that are not properly acknowledged (e.g., dropped messages). In contrast, the network protocol does not monitor non-reliable messages for drops, nor re-transmit them. To facilitate network tuning, the network communication protocol uses data from the acknowledge messages of selected reliable and non-reliable messages to gather operational data about the shared link, including data used to detect link saturation, calculate outbound bandwidth, and adjust the message send rate. Both the reliable and non-reliable channels share the same link by using the same transport layer protocol, preferably a datagram protocol such as UDP.
In another aspect of the invention, the network protocol determines the available bandwidth on this shared link. In response to requests from an application program, the network communication protocol sends critical data over the reliable channel and non-critical data over the non-reliable channel of the shared link. To maintain operational characteristics about the link, the network protocol requests an acknowledge message for certain outbound messages, including selected reliable messages and non-reliable messages sent on the shared link. Each of these outbound messages is timestamped with the time the message was sent according to the local computer""s clock, and includes a message identifier. Each acknowledge message is timestamped with the time it is sent from the remote computer, and includes a count of the data (e.g., count of bytes) received for the outbound message and an identifier that matches the message identifier of the outbound message that it corresponds to. The message identifier is used to ensure that the acknowledgement messages are correctly matched with outbound messages.
The network protocol maintains a variety of operational characteristics of the shared link. For example in the current implementation, it calculates a clock bias between the clocks of the local and remote computers based on the time the outbound messages are sent and the time they are received by comparing the outbound message timestamps to the acknowledge message timestamps. The rate that all messages (including the reliable and non-reliable messages) are sent is increased until the link becomes saturated, which is detected by observing an increase in a measure of the round-trip latency and changes in the clock bias. At link saturation, the network protocol tracks the total data received in the remote computer between two acknowledge messages. It then calculates the outbound bandwidth of the link by dividing the data received in the remote computer by the time over which that data was received.
The network protocol and associated methods allow application programs to maximize the use of available network bandwidth, thereby improving the performance of the programs"" communications. The network protocol sends reliable and non-critical messages over respective reliable and non-reliable channels that share a network link. While sending these messages, the network protocol increases the send rate of the messages according to a predetermined scheme until it detects link saturation. The protocol also continuously pushes up the send rate until message dropouts are detected, at which point it makes a step reduction of the send rate, and starts pushing up the send rate again. The link saturation and detection may also result from increased link usage by other users on the network. At link saturation, the protocol calculates the outbound bandwidth of the link, and reduces the message send rate to the calculated bandwidth. It also calculates a wait time to clear backlogged messages. After the wait time, the protocol sets the message send rate to the calculated bandwidth, and resumes the sending of messages. The process preferably is repeated on a continual basis so as to adjust the message send rate to take advantage of the latest bandwidth and backlog measurements.
The foregoing methods can also be utilized in scenarios where more than two computers are linked in communication across a network, such as the case that exists when multiple players in a peer-to-peer relationship to one another are playing a game over a network. The message send rate can be tuned for each peer-to-peer relationship, maximizing the use of available bandwidth across the peer-to-peer link.
Further advantages and features of the invention will become apparent with reference to the following detailed description and accompanying drawings.